/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package berkeley.project1;

/* RunLengthEncoding.java */

/**
 *  The RunLengthEncoding class defines an object that run-length encodes an
 *  Ocean object.  Descriptions of the methods you must implement appear below.
 *  They include constructors of the form
 *
 *      public RunLengthEncoding(int i, int j, int starveTime);
 *      public RunLengthEncoding(int i, int j, int starveTime,
 *                               int[] runTypes, int[] runLengths) {
 *      public RunLengthEncoding(Ocean ocean) {
 *
 *  that create a run-length encoding of an Ocean having width i and height j,
 *  in which sharks starve after starveTime timesteps.
 *
 *  The first constructor creates a run-length encoding of an Ocean in which
 *  every cell is empty.  The second constructor creates a run-length encoding
 *  for which the runs are provided as parameters.  The third constructor
 *  converts an Ocean object into a run-length encoding of that object.
 *
 *  See the README file accompanying this project for additional details.
 */

public class RunLengthEncoding {

  /**
   *  Define any variables associated with a RunLengthEncoding object here.
   *  These variables MUST be private.
   */

  private int i, j, starveTime;
  private DList list;
  private int currentPos;

  /**
   *  The following methods are required for Part II.
   */

  /**
   *  RunLengthEncoding() (with three parameters) is a constructor that creates
   *  a run-length encoding of an empty ocean having width i and height j,
   *  in which sharks starve after starveTime timesteps.
   *  @param i is the width of the ocean.
   *  @param j is the height of the ocean.
   *  @param starveTime is the number of timesteps sharks survive without food.
   */

  public RunLengthEncoding(int i, int j, int starveTime) {
    this.i = i;
    this.j = j;
    this.starveTime = starveTime;
    list = new DList();
  }

  /**
   *  RunLengthEncoding() (with five parameters) is a constructor that creates
   *  a run-length encoding of an ocean having width i and height j, in which
   *  sharks starve after starveTime timesteps.  The runs of the run-length
   *  encoding are taken from two input arrays.  Run i has length runLengths[i]
   *  and species runTypes[i].
   *  @param i is the width of the ocean.
   *  @param j is the height of the ocean.
   *  @param starveTime is the number of timesteps sharks survive without food.
   *  @param runTypes is an array that represents the species represented by
   *         each run.  Each element of runTypes is Ocean.EMPTY, Ocean.FISH,
   *         or Ocean.SHARK.  Any run of sharks is treated as a run of newborn
   *         sharks (which are equivalent to sharks that have just eaten).
   *  @param runLengths is an array that represents the length of each run.
   *         The sum of all elements of the runLengths array should be i * j.
   */

  public RunLengthEncoding(int i, int j, int starveTime,
                           int[] runTypes, int[] runLengths) {
    this(i, j, starveTime);
    for (int n = 0; n < runTypes.length; n++) {
        int[] run = new int[3];
        run[0] = runTypes[n];
        run[1] = runLengths[n];
        run[2] = (runTypes[n] == Ocean.SHARK) ? starveTime : 0;
        list.insertEnd(run);
    }
  }

  /**
   *  restartRuns() and nextRun() are two methods that work together to return
   *  all the runs in the run-length encoding, one by one.  Each time
   *  nextRun() is invoked, it returns a different run (represented as an
   *  array of two ints), until every run has been returned.  The first time
   *  nextRun() is invoked, it returns the first run in the encoding, which
   *  contains cell (0, 0).  After every run has been returned, nextRun()
   *  returns null, which lets the calling program know that there are no more
   *  runs in the encoding.
   *
   *  The restartRuns() method resets the enumeration, so that nextRun() will
   *  once again enumerate all the runs as if nextRun() were being invoked for
   *  the first time.
   *
   *  (Note:  Don't worry about what might happen if nextRun() is interleaved
   *  with addFish() or addShark(); it won't happen.)
   */

  /**
   *  restartRuns() resets the enumeration as described above, so that
   *  nextRun() will enumerate all the runs from the beginning.
   */

  public void restartRuns() {
    currentPos = 0;
  }

  /**
   *  nextRun() returns the next run in the enumeration, as described above.
   *  If the runs have been exhausted, it returns null.  The return value is
   *  an array of two ints (constructed here), representing the type and the
   *  size of the run, in that order.
   *  @return the next run in the enumeration, represented by an array of
   *          two ints.  The int at index zero indicates the run type
   *          (Ocean.EMPTY, Ocean.SHARK, or Ocean.FISH).  The int at index one
   *          indicates the run length (which must be at least 1).
   */

  public int[] nextRun() {
    if (currentPos >= list.size) {
        return null;
    }
    int[] currentElement = list.nth(currentPos++).getItem();
    int[] run = {currentElement[0], currentElement[1]};
    return run;
  }

  /**
   *  toOcean() converts a run-length encoding of an ocean into an Ocean
   *  object.  You will need to implement the three-parameter addShark method
   *  in the Ocean class for this method's use.
   *  @return the Ocean represented by a run-length encoding.
   */

  public Ocean toOcean() {
    Ocean ocean = new Ocean(i, j, starveTime);
    int x = 0; // for iterating
    for (int n = 0; n < list.size; n++) {
        int[] element = list.nth(n).getItem();
        switch (element[0]) {
            case Ocean.EMPTY :
                int length = element[1];
                while (length > 0) {
                    x++;
                    length--;
                }
                break;
            case Ocean.FISH :
                length = element[1];
                while (length > 0) {
                    ocean.addFish(x%i, x/i);
                    x++;
                    length--;
                }
                break;
            case Ocean.SHARK :
                length = element[1];
                while (length > 0) {
                    ocean.addShark(x%i, x/i, element[2]);
                    x++;
                    length--;
                }
                break;
        }
    }
    return ocean;
  }

  /**
   *  The following method is required for Part III.
   */

  /**
   *  RunLengthEncoding() (with one parameter) is a constructor that creates
   *  a run-length encoding of an input Ocean.  You will need to implement
   *  the sharkFeeding method in the Ocean class for this constructor's use.
   *  @param sea is the ocean to encode.
   */

  public RunLengthEncoding(Ocean sea) {
    this(sea.width(), sea.height(), sea.starveTime());
    int x = 0, y = 0;
    int currentLength = 0, currentType = sea.cellContents(0, 0), currentSharkFeeding = 0;
    for (y = 0; y < j; y++) {
        for (x = 0; x < i; x++) {
            if (currentType != sea.cellContents(x, y) ||
                    (currentType == Ocean.SHARK && currentSharkFeeding != sea.sharkFeeding(x, y))) {
                insertNextRun(currentType, currentLength, currentSharkFeeding);
                currentType = sea.cellContents(x, y);
                currentSharkFeeding = (currentType == Ocean.SHARK) ? sea.sharkFeeding(x, y) : 0;
                currentLength = 1;
            } else {
                currentLength++;
            }
        }
    }
    insertNextRun(currentType, currentLength, currentSharkFeeding);
    check();
  }
  
  private void insertNextRun(int currentType, int currentLength, int sharkFeeding) {
      int[] temp = new int[3];
      temp[0] = currentType;
      temp[1] = currentLength;
      temp[2] = sharkFeeding;
      list.insertEnd(temp);
  }

  /**
   *  The following methods are required for Part IV.
   */

  /**
   *  addFish() places a fish in cell (x, y) if the cell is empty.  If the
   *  cell is already occupied, leave the cell as it is.  The final run-length
   *  encoding should be compressed as much as possible; there should not be
   *  two consecutive runs of sharks with the same degree of hunger.
   *  @param x is the x-coordinate of the cell to place a fish in.
   *  @param y is the y-coordinate of the cell to place a fish in.
   */

  public void addFish(int x, int y) {
    addEntity(x, y, Ocean.FISH);
  }
  
  private void addEntity(int x, int y, int type) {
    int index = i * y + x + 1; // general index in consequence
    int currentSize = 0;
    DListNode currentNode = list.nth(0);
    for (int n = 0; n < list.size; n++) {
        currentNode = list.nth(n);
        currentSize += currentNode.getItem()[1];
        if (index <= currentSize) {
            break;
        }
    }
    int entityStarveTime = (type == Ocean.SHARK) ? starveTime : 0;
    
    if (currentNode.getItem()[0] != Ocean.EMPTY) {
        return; // nothing changes if cell is occupied
    } else {
        int runsLength = currentNode.getItem()[1];
        int innerIndex = index - (currentSize - runsLength) - 1;
        int[] currentNodeItem = currentNode.getItem();
        
        DListNode prevNode = currentNode.prev, nextNode = currentNode.next;
        
        // insert new element into current node
        if (currentNodeItem[1] == 1) {
            currentNodeItem[0] = type;
            currentNodeItem[2] = entityStarveTime; // init feed, for fish is always 0
        } else {
            if (innerIndex == 0) {
                DListNode node1 = new DListNode(new int[] {type, 1, entityStarveTime});
                currentNodeItem[1]--;
                list.insertBefore(currentNode, node1);
            } else {
                DListNode node1 = new DListNode(new int[] {Ocean.EMPTY, innerIndex, 0});
                list.insertBefore(currentNode, node1);
                if (innerIndex != currentNodeItem[1] - 1) {
                    DListNode node2 = new DListNode(new int[] {Ocean.EMPTY, currentNodeItem[1] - innerIndex - 1, 0});
                    list.insertAfter(currentNode, node2);
                }
                // init new ENTITY of specified type
                currentNodeItem[0] = type;
                currentNodeItem[1] = 1;
                currentNodeItem[2] = entityStarveTime;
            }
        }
        merge(prevNode, nextNode);

    }
    check();
  }
  
  private void merge(DListNode from, DListNode to) {
      DListNode currentNode = from;
      while (currentNode != null && currentNode.next != to.next) {
          if (currentNode.item[0] == currentNode.next.item[0] && currentNode.item[2] == currentNode.next.item[2]) {
              currentNode.item[1] += currentNode.next.item[1];
              list.removeCurrentNode(currentNode.next);
          } else {
            currentNode = currentNode.next;
          }
      }
  }

  /**
   *  addShark() (with two parameters) places a newborn shark in cell (x, y) if
   *  the cell is empty.  A "newborn" shark is equivalent to a shark that has
   *  just eaten.  If the cell is already occupied, leave the cell as it is.
   *  The final run-length encoding should be compressed as much as possible;
   *  there should not be two consecutive runs of sharks with the same degree
   *  of hunger.
   *  @param x is the x-coordinate of the cell to place a shark in.
   *  @param y is the y-coordinate of the cell to place a shark in.
   */

  public void addShark(int x, int y) {
    addEntity(x, y, Ocean.SHARK);
  }

  /**
   *  check() walks through the run-length encoding and prints an error message
   *  if two consecutive runs have the same contents, or if the sum of all run
   *  lengths does not equal the number of cells in the ocean.
   */

  private void check() {
      checkConsecutives();
      checkListSize();
      checkRunLength();
  }
  
  private void checkConsecutives() {
      int[] currentEntity = list.nth(0).getItem();
      int currentType = currentEntity[0];
      int currentSharkFeeding = currentEntity[2];
      for (int x = 1; x < list.size; x++) {
          currentEntity = list.nth(x).getItem();
          if (currentEntity[0] == currentType && (currentType != Ocean.SHARK ||
                  currentEntity[2] == currentSharkFeeding)) {
              System.out.println("Consecutive types are wrong. No cookeis");
          }
          currentType = currentEntity[0];
          currentSharkFeeding = currentEntity[2];
      }
  }
  
  private void checkListSize() {
      int size = 0;
      for (int x = 0; x < list.size; x++) {
          int[] currentEntity = list.nth(x).getItem();
          size += currentEntity[1];
      }
      if (size != i * j) {
          System.out.println("List size is wrong. No cookies");
      }
  }
  
  private void checkRunLength() {
       for (int x = 0; x < list.size; x++) {
          int[] currentEntity = list.nth(x).getItem();
          if (currentEntity[1] < 1) {
              System.out.println("Run's length can't be less than 1");
          }
      }
  }

}
